Technical Field
Embodiments described herein relate to data processing and more particularly, to systems and methods of efficiently managing data structures in a computing system.
Description of the Related Art
Shared data structures, such as queues, are often used to facilitate communication between entities, such as tasks or threads, in computing systems. However, managing the insertion and deletion of data in a shared data structure by multiple entities operating in parallel is difficult to coordinate. Existing implementations often use locks to coordinate manipulations of the shared data structure. Other implementations rely on techniques such as pre-calculation of offsets at which each thread would access the data structure (e.g., using prefix-sums), but add complexity and software overheads. In highly parallel environments, contention for shared data structures can be a significant performance bottleneck.